Os testes computacionais foram executados em computadores QuadCore i5 com 8GB de mem\'oria. As inst\^ancias 
s\~ao as descritas na se\c c\~ao anterior. 

Para o teste da Tabela \ref{tab:const1_2} foram executadas 100 itera\c c\~oes para 10 sementes diferentes.A primeira coluna cont\'em o nome da inst\^ancia, a segunda e a quarta colunas mostram os melhores valores encontrados entre as 10 sementes e a terceira e a quinta colunas apresentam as m\'edias dos valores das 10 sementes.

\begin{table}[!ht]
\small
\centering
\begin{tabular}{lcccccc}
\hline 
& \multicolumn{2}{c}{Fase 1} & \multicolumn{2}{c}{Fase 2}\\
Inst\^ancia & Custo* & Custo M\'edio & Custo* & Custo M\'edio\\
\hline
Agg-A1 & 13 & 15,10 & 13 & {\bf 14,32} \\
Agg-A2 & 15 & 20,36 & 15 & {\bf 19,91} \\
Agg-B1 & 38 & 50,83 & 38 & {\bf 49,53} \\
Agg-B2 & 29 & 40,75 & {\bf 26} & {\bf 36,58} \\
Agg-C1 & 64 & 78,41 & {\bf 59} & {\bf 72,85} \\
Agg-C2 & 37 & 48,66 & {\bf 36} & {\bf 44,31} \\
Agg-D1 & 75 & 88,84 & {\bf 69} & {\bf 80,20} \\
Agg-D2 & 55 & 68,43 & {\bf 49} & {\bf 59,71} \\
Agg-E1 & 77 & 94,54 & {\bf 69} & {\bf 85,14} \\
Agg-E2 & 69 & 90,43 & {\bf 62} & {\bf 80,33} \\
Agg-F1 & 177 & 209,18 & {\bf 168} & {\bf 192,26} \\
Agg-F2 & 154 & 186,16 & {\bf 142} & {\bf 169,47} \\
Agg-G1 & 341 & 373,15 & {\bf 305} & {\bf 340,81} \\
Agg-G2 & 336 & 366,48 & {\bf 304} & {\bf 333,76} \\
\hline
\end{tabular}
\caption{Compara\c c\~ao Constru\c c\~ao: Fase 1 e Fase 2}
\label{tab:const1_2}
\end{table}

Na Tabela \ref{tab:const1_2}, o objetivo \'e comparar a qualidade da solu\c c\~ao ao final do passo 3 da constru\c c\~ao (aqui chamado de Fase 1) e a qualidade da solu\c c\~ao ao final do passo 4 da constru\c c\~ao (chamado de Fase 2). Como resultado, nota-se que a estrat\'egia da Fase 2, que descarta as arestas da solu\c c\~ao da Fase1, foi mais eficiente para 11 das 14 inst\^ancias, sendo que as demais encontraram o mesmo valor. As m\'edias dos valores da Fase 2 tamb\'em foram melhores para todas as inst\^ancias. 

Para os testes das tabelas \ref{tab:grasp1_3} e \ref{tab:grasp1_4} foram executadas 100 itera\c c\~oes de cada estrat\'egia para 10 
sementes diferentes. Em cada tabela, a primeira coluna tem o nome da inst\^ancia, a segunda e a 
quinta colunas mostram os melhores valores encontrados dentre as 10 sementes, a terceira e na 
sexta colunas t\^em as m\'edias dos valores das 10 sementes e nas quartas e s\'etima colunas 
s\~ao apresentados os tempos m\'edios das 10 sementes.

\begin{table}[!ht]
\small
\centering
\begin{tabular}{lcccccc}
\hline 
& \multicolumn{3}{c}{GRASP-FULL} & \multicolumn{3}{c}{GRASP-PART2}\\
Inst\^ancia & Melhor & M\'edia & Tempo & Melhor & M\'edia & Tempo\\
\hline
Agg-A1 & 13 & 13,00 & {\bf 0000,0164} & 13 & 13,00 & 0000,0242 \\
Agg-A2 & 15 & 15,00 & {\bf 0000,0156} & 15 & 15,00 & 0000,0237 \\
Agg-B1 & 38 & 38,00 & {\bf 0000,1364} & 38 & 38,00 & 0000,2072 \\
Agg-B2 & 26 & 26,00 & {\bf 0000,1640} & 26 & 26,00 & 0000,2443 \\
Agg-C1 & 57 & 58,60 & {\bf 0000,8519} & 57 & {\bf 58,30} & 0000,8613 \\
Agg-C2 & 35 & 35,40 & 0000,9326 & 34 & {\bf 35,30} & {\bf 0000,8977} \\
Agg-D1 & 69 & 69,00 & 0002,2429 & 69 & 69,00 & {\bf 0002,2334} \\
Agg-D2 & 44 & {\bf 46,90} & 0002,7291 & 44 & 47,00 & {\bf 0002,6802} \\
Agg-E1 & 64 & 66,60 & 0005,6251 & 64 & {\bf 66,40} & {\bf 0005,5642} \\
Agg-E2 & 54 & 57,70 & 0006,5761 & 54 & {\bf 57,20} & {\bf 0006,4780} \\
Agg-F1 & 162 & 167,30 & 0101,5530 & 162 & {\bf 167,10} & {\bf 0100,6190} \\
Agg-F2 & 133 & 136,40 & 0107,3960 & {\bf 131} & {\bf 136,30} & {\bf 0106,3470} \\
Agg-G1 & 290 & 298,30 & 1866,2400 & 290 & {\bf 297,60} & {\bf 1800,8300} \\
Agg-G2 & 292 & 300,00 & 1662,5100 & {\bf 291} & {\bf 298,60} & {\bf 1661,4600} \\
\hline
\end{tabular}
\caption{Compara\c c\~ao Duas Parti\c c\~oes}
\label{tab:grasp1_3}
\end{table}

\begin{table}[!ht]
\small
\centering
\begin{tabular}{lcccccc}
\hline 
& \multicolumn{3}{c}{GRASP-FULL} & \multicolumn{3}{c}{GRASP-PART3}\\
Inst\^ancia & Melhor & M\'edia & Tempo & Melhor & M\'edia & Tempo\\
\hline
Agg-A1 & 13 & 13,00 & {\bf 0000,0164} & 13 & 13,00 & 0000,0245 \\
Agg-A2 & 15 & 15,00 & {\bf 0000,0156} & 15 & 15,00 & 0000,0253 \\
Agg-B1 & 38 & 38,00 & {\bf 0000,1364} & 38 & 38,00 & 0000,2301 \\
Agg-B2 & 26 & 26,00 & {\bf 0000,1640} & 26 & 26,00 & 0000,2716 \\
Agg-C1 & 57 & 58,60 & {\bf 0000,8519} & 57 & {\bf 58,30} & 0000,9487 \\
Agg-C2 & 35 & 35,40 & 0000,9326 & {\bf 34} & {\bf 35,20} & {\bf 0000,9247} \\
Agg-D1 & 69 & 69,00 & {\bf 0002,2429} & 69 & 69,00 & 0002,2975 \\
Agg-D2 & 44 & 46,90 & {\bf 0002,7291} & 44 & {\bf 46,80} & 0002,8189 \\
Agg-E1 & 64 & 66,60 & 0005,6251 & 64 & {\bf 65,60} & {\bf 0005,5193} \\
Agg-E2 & 54 & 57,70 & 0006,5761 & {\bf 52} & {\bf 56,00} & {\bf 0006,4920} \\
Agg-F1 & 162 & 167,30 & {\bf 0101,5530} & {\bf 161} & {\bf 166,10} & 0101,5760 \\
Agg-F2 & 133 & 136,40 & 0107,3960 & {\bf 131} & {\bf 134,00} & {\bf 0105,9010} \\
Agg-G1 & 290 & 298,30 & 1866,2400 & {\bf 285} & {\bf 294,00} & {\bf 1835,3800} \\
Agg-G2 & 292 & 300,00 & 1662,5100 & {\bf 289} & {\bf 296,30} & {\bf 1654,8700} \\
\hline
\end{tabular}
\caption{Compara\c c\~ao Tr\^es Parti\c c\~oes}
\label{tab:grasp1_4}
\end{table}


\begin{table}[!ht]
\small
\centering
\begin{tabular}{lccccc}
\hline 
& \multicolumn{2}{c}{Sem SC} & \multicolumn{2}{c}{Com SC}\\
Inst\^ancia & Dual & Tempo & Dual & Tempo \\
\hline
Agg-A1 & 13,00 & 0000,008 & 13,00 & 0000,012 \\
Agg-A2 & 14,00 & 0000,008 & {\bf 14,00} & 0000,008 \\
Agg-B1 & 36,50 & 0000,028 & {\bf 36,86} & 0000,152 \\
Agg-B2 & 25,25 & 0000,012 & {\bf 25,57} & 0000,112 \\
Agg-C1 & 56,20 & 0000,088 & {\bf 56,22} & 0000,388 \\
Agg-C2 & 34,00 & 0000,136 & 34,00 & 0000,480 \\
Agg-D1 & 68,60 & 0000,196 & {\bf 69,00} & 0002,552 \\
Agg-D2 & 41,13 & 0000,320 & {\bf 41,25} & 0000,888 \\
Agg-E1 & 62,67 & 0000,336 & 62,67 & 0000,852 \\
Agg-E2 & 47,00 & 0001,100 & 47,00 & 0001,932 \\
Agg-F1 & 153,00 & 0021,101 & 153,00 & 0013,121 \\
Agg-F2 & 111,00 & 0002,852 & {\bf 111,00} & 0004,832 \\
Agg-G1 & 245,00 & * & 245,00 & * \\
Agg-G2 & 252,00 & * & 252,00 & * \\
\hline
\end{tabular}
\caption{Compara\c c\~ao entre os Limites Dual e Primal}
\label{tab:dual}
\end{table}

\begin{table}[!ht]
\small
\centering
\begin{tabular}{lcccccc}
\hline 
Inst\^ancia & Dual & Tempo & Primal & Tempo & Gap(\%)\\
\hline
Agg-A1 & 13,00 & 0000,012 & 13 & 0000,025 & OPT \\
Agg-A2 & {\bf 14,00} & 0000,008 & 15 & 0000,025 & 7,142 \\
Agg-B1 & 36,86 & 0000,152 & 38 & 0000,230 & 3,093 \\
Agg-B2 & 25,57 & 0000,112 & 26 & 0000,272 & OPT \\
Agg-C1 & 56,22 & 0000,388 & 57 & 0000,949 & OPT \\
Agg-C2 & 34,00 & 0000,480 & 34 & 0000,925 & OPT \\
Agg-D1 & 69,00 & 0002,552 & 69 & 0002,298 & OPT \\
Agg-D2 & 41,25 & 0000,888 & 44 & 0002,819 & 6,666 \\
Agg-E1 & 62,67 & 0000,852 & 64 & 0005,519 & 2,122 \\
Agg-E2 & 47,00 & 0001,932 & 52 & 0006,492 & 10,638 \\
Agg-F1 & 153,00 & 0013,121 & 161 & 0101,576 & 5,229 \\
Agg-F2 & {\bf 111,00} & 0004,832 & 131 & 0105,901 & 18,018 \\
Agg-G1 & 245,00 & * & 285 & 1835,380 & 16,326 \\
Agg-G2 & 252,00 & * & 289 & 1654,870 & 14,682 \\
\hline
\end{tabular}
\caption{Compara\c c\~ao entre os Limites Dual e Primal}
\label{tab:limites}
\end{table}

\begin{figure}[h!]
  \begin{center}
    \subfigure[Um alvo m\'edio para a inst\^ancia Agg-E2]{\label{fig:tttmedio} \includegraphics[width=.84\textwidth]{ttt-plot_medio.eps}}
    \subfigure[Um alvo dif\'{\i}cil para a inst\^ancia Agg-E2]{\label{fig:tttdificil} \includegraphics[width=.84\textwidth]{ttt-plot_dificil.eps}}
  \end{center}
  \caption{Gr\'aficos Time-to-target}
  \label{fig:timetotarget}
\end{figure}

\begin{figure}[h!]
  \begin{center}
    \subfigure[Um alvo m\'edio para a inst\^ancia Agg-E2]{\label{fig:semmedio} \includegraphics[width=.84\textwidth]{tempsem_medio.eps}}
    \subfigure[Um alvo dif\'{\i}cil para a inst\^ancia Agg-E2]{\label{fig:semdificil} \includegraphics[width=.84\textwidth]{tempsem_dificil.eps}}
  \end{center}
  \caption{Gr\'aficos com Tempo em cada Semente}
  \label{fig:sem}
\end{figure}

Na Tabela \ref{tab:grasp1_3} o GRASP-FULL, implementado com a buscal local original, \'e comparado ao GRASP-PART2, implementado com a 
busca local particionada em dois n\'iveis. Como resultado, \'e poss\'ivel ver uma melhora no tempo de execu\c c\~ao, nas m\'edias dos custos das 
solu\c c\~oes e para as inst\^ancias Agg-F2 e Agg-G2 ainda foi poss\'ivel melhorar a melhor solu\c c\~ao.


Na Tabela \ref{tab:grasp1_4} o GRASP-FULL, implementado com a buscal local original, \'e comparado ao GRASP-PART3, implementado com a 
busca local particionada em tr\^es n\'iveis. Como
resultado \'e poss\'ivel ver que houve uma melhora no tempo de execu\c c\~ao para as inst\^ancias maiores. 
J\'a para a m\'edias dos custos das solu\c c\~oes, melhoramos os resultados em todas as inst\^ancias a partir
da Agg-C1 (na inst\^ancia Agg-D1 $69$ \'e o valor \'otimo). Quanto ao melhor valor encontrado,
podemos notar que em 6 inst\^ancias conseguimos encontrar solu\c c\~oes melhores.


Na Tabela \ref{tab:dual}, \'e analisado o impacto do uso de cortes de cobertura (SC) durante o algoritmo de 
separa\c c\~ao. Como mostrado na tabela conseguimos melhorar resultados de 7 inst\^ancias. Para as inst\^ancias 
Agg-A2 e Agg-F2, apesar de encontrar o mesmo valor, conseguimos eliminar a solu\c c\~ao n\~ao inteira e dessa 
forma provar os valores \'otimos para essas inst\^ancias.

Na Tabela \ref{tab:limites} foram comparados os valores encontrados pela estrat\'egia GRASP-PART3 e
os valores encontrados pelo algoritmo de separa\c c\~ao. Para encontrar os limites duais foi estipulado um 
tempo limite de 200 segundos. As inst\^ancias com tempo $*$ tiveram suas execu\c c\~oes paradas por esse motivo.
Nessa tabela conseguimos provar o \'otimo 
de 5 inst\^ancias e chegar perto de outros, mas para algumas inst\^ancias ainda existe um GAP muito alto. 
Paras as inst\^ancias Agg-A2 e Agg-F2 a otimalidade foi provada pela integralidade da solu\c c\~ao encontrada, 
totalizando 7 \'otimos encontrados.


As Figuras~\ref{fig:tttmedio} e \ref{fig:tttdificil} 
mostram outra compara\c c\~ao entre as tr\^es estrat\'egias, 
baseada nos gr\'aficos $time$-$to$-$target$ (TTT) ~\cite{Aiex}, que s\~ao usados 
para fazer an\'alise de comportamento de algoritmos aleat\'orios.
Esses gr\'aficos basicamente mostram as distribui\c c\~oes de probabilidade acumulada de tempos de execu\c c\~ao, 
ou seja, $p($tempo\_computacional$ < x)$ vs. $x$.
 
Para gerar um gr\'afico TTT, executa-se um algoritmo algumas vezes e mede-se o tempo 
necess\'ario para atingir uma solu\c c\~ao com um valor melhor ou igual a um valor alvo.
Nos experimentos apresentados neste trabalho, cada estrat\'egia foi executada 100 vezes.
Os tempos obtidos s\~ao ordenados de forma crescente e ao $i$-\'esimo tempo $t_i$ \'e associado o valor 
de probabilidade $p_i=(i-1/2)/100$.
Os pontos $z_i = (t_i,p_i)$, para $i = 1,. . . ,100$, s\~ao tra\c cados no gr\'afico, 
indicando a probabilidade (eixo vertical) de uma estrat\'egia atingir uma solu\c c\~ao alvo em um tempo 
indicado (eixo horizontal).
Os gr\'aficos apresentados nas Figuras~\ref{fig:tttmedio} e \ref{fig:tttdificil} 
foram gerados a partir das execu\c c\~oes do GRASP-FULL, GRASP-PART2 e GRASP-PART3, para a 
inst\^ancia Agg-E2, usando um alvo de dificuldade m\'edia (55) e um alvo dif\'{\i}cil (53).


Para o alvo m\'edio, pode-se observar na Figura~\ref{fig:tttmedio} que o
GRASP-FULL apresentou o pior comportamento e que o GRASP-PART3 apresentou o melhor desempenho. 
Pode-se verificar que a probabilidade do GRASP-PART3 atingir o alvo m\'edio em aproximadamente 55 segundos 
\'e 100\%, do GRASP-PART2 \'e aproximadamente ~95\% e do GRASP-FULL \'e de aproximadamente ~90\%.
Para o alvo dif\'{\i}cil, a Figura~\ref{fig:tttdificil} mostra que o GRASP-PART3 obteve o melhor comportamento.
Esse gr\'afico indica que GRASP-PART3 consegue encontrar solu\c c\~oes dif\'{\i}ceis mais rapidamente que 
o GRASP-PART2 e muito mais rapidamente que o GRASP-FULL, demonstrando que particionar a busca local 
mais de uma vez proporcionou maior robustez para a estrat\'egia.


Com os mesmos tempos usados para gerar os gr\'aficos TTT, fizemos uma an\'alise gr\'afica dos
tempos que cada semente demorou para atingir o alvo. Nas Figuras ~\ref{fig:semmedio} e ~\ref{fig:semdificil}, o eixo vertical indica o tempo que a semente do eixo horizontal demorou para atingir o alvo. Desses gr\'aficos podemos notar que a estrat\'egia
GRASP-PART3 n\~ao sofreu tanta varia\c c\~ao quanto o GRASP-FULL, confirmando que o m\'etodo torna a busca local 
mais robusta.

